#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

void quicksort(int* list, int start, int end);

int main()
{
	int N = 0;
	
	// Ask user for size of problem
	cout<<"Please enter the number of integers to sort..."<<endl;
	cin>>N;
	if(!(N>0) || !(N<INT_MAX)){
		cout<<"ERROR - Input must be between 1 and MAX_INT"<<endl;
		exit(1);}

	// Allocate space	
	int* list = (int*)malloc(sizeof(int)*N);

	// Seed RNG
	srand((unsigned)time(0));

	// Generate and print problem
	cout<<"Set of integers, unsorted, is..."<<endl;
	for(int i = 0; i < N; i++){
		list[i] = rand()%1000;
		cout<<list[i]<<" ";}
	cout<<endl;
	
	// Perform sort
	quicksort(list,0,N-1);

	// Print result
	cout<<endl<<"Sorted List..."<<endl;
	for(int i = 0; i < N; i++)
		cout<<list[i]<<" ";
	cout<<endl;

	// Make sure list is actually sorted
	cout<<endl<<"Checking for validity..."<<endl;
	for(int i  = 0; i < N-1; i++)
	{
		if(list[i] > list[i+1]){
			cout<<"Uh oh... list isn't sorted correctly!"<<endl;
			exit(1);}
	}
	
	cout<<"Everything checked out, list is sorted!"<<endl<<endl;
	free(list);
}

// Recursive algorithm to quicksort a set of integers in-place.
// First, move the pivot to the end of the list and partition the list
// accordingly. Do the same for the new partitions
void quicksort(int* list, int start, int end)
{
	// One of the base cases... usually occurs if first pivot is largest element
	// or if the right subset of a partition is size = 0
	if(start >= end) return;

	// Other base case where only two elements remain in a set
	// Swap them if necessary, then return
	if(end-start == 1)
	{
		if(list[start] > list[end])
		{
			int temp = list[start];
			list[start] = list[end];
			list[end] = temp;
			return;		
		}
		
		else return;
	}
	
	// For this algorithm, the pivot is always the end of a sublist
	
	int pivotPos = end;
	
	// Randomizing pivot breaks the program for some reason... look into this
	//int pivotPos = start == 0 ? rand()%(end+1) : (rand()%(end-start+1))+start;

	int pivotVal = list[pivotPos];
	int swapIndex = start;
	
	// Go through every other element and see if we need to move
	// it to the left of the pivot
	for(int i = start; i < end; i++)
	{
		if(list[i] <= pivotVal)
		{
			//cout<<"Swapping "<<list[i]<<" with "<<list[swapIndex]<<endl;
			int temp = list[swapIndex];
			list[swapIndex] = list[i];
			list[i] = temp;
			swapIndex++;	
		}
	}

	// Swap back old pivot to its correct position in the final list
	list[end] = list[swapIndex];
	list[swapIndex] = pivotVal;

	// Sort left and right sublists
	quicksort(list,0,swapIndex-1);
	quicksort(list,swapIndex+1,end);
}






